/**
 * https://leetcode.cn/problems/reverse-linked-list/description/
 */
class ListNode {
    int val;
    ListNode next;

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(64);
        sb.append("[");
        ListNode p = this;
        while (p != null) {
            sb.append(p.val);
            if (p.next != null) {
                sb.append(",");
            }
            p = p.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

/**
 * @author liuzhaoqiang
 */
public class LeetCode206 {
    /**
     * 遍历连表 然后在重新创建一个连表使用头插入法
     * @param o1
     * @return
     */
    public ListNode reverseList1(ListNode o1) {
        ListNode p = o1;
        ListNode n1 = null;
        while(p!=null){
            n1 = new ListNode(p.val,n1);
            p = p.next;
        }
        return n1;
    }

    /**
     * 构造一个新链表，从旧链表头部移除节点，添加到新链表头，
     * 完成后新链表即是倒序的，区别在于原题目未提供节点外层的容器类，
     * 这里提供一个，另外一个区别是并不去构造新节点
     * @param o1
     * @return
     */
    public ListNode reverseList2(ListNode o1) {
       List list1 = new List(o1);
       List list2 = new List(null);
       while(true){
           ListNode first = list1.removeFirst();
           if(first==null){
               break;
           }
           list2.addFirst(first);
       }
       return list2.head;
    }
    //递归 找到最后一个节点返回
    public ListNode reverseList(ListNode o1){
        if(o1 == null || o1.next == null){
            return o1;
        }
        ListNode lastNode = reverseList(o1.next);
        o1.next.next = o1;
        o1.next = null;
        return lastNode;
    }

    static class List{
        ListNode head;
        public List(ListNode head){
            this.head = head;
        }

        public void addFirst(ListNode first){
            first.next = head;
            head = first;
        }

        public ListNode removeFirst(){
            ListNode first = head;
            if(first!=null){
                head = first.next;
            }
            return first;
        }
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
        ListNode n1 = new LeetCode206().reverseList(o1);
        System.out.println(n1);
    }
}

